home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1999 March / EnigmA AMIGA RUN 35 (1999)(G.R. Edizioni)(IT)[!][issue 1999-03].iso / earcd / devel / vbcc-src / cse.c < prev    next >
C/C++ Source or Header  |  1999-01-01  |  13KB  |  377 lines
  1. /*  $VER: vbcc (cse.c) V0.4     */
  2. /*  verfuegbare Ausdruecke und common subexpression elimination */
  3.  
  4. #include "opt.h"
  5.  
  6. static char FILE_[]=__FILE__;
  7.  
  8. /*  fuer verfuegbare Ausdruecke */
  9. struct IC **elist;
  10. unsigned int ecount;
  11. size_t esize;
  12. unsigned char *ae_globals,*ae_statics,*ae_address,*ae_drefs;
  13. unsigned char **ae_kills;
  14.  
  15. void available_expressions(struct flowgraph *fg)
  16. /*  berechnet die verfuegbaren Ausdruecke fuer jeden Block      */
  17. {
  18.     struct flowgraph *g;struct IC *p;unsigned char *tmp;
  19.     int changed,pass,i,j;
  20.     /*  ae_gen und ae_kill fuer jeden Block berechnen   */
  21.     if(DEBUG&1024) printf("analysing available expressions\n");
  22.     tmp=mymalloc(esize);
  23.     g=fg;
  24.     while(g){
  25.         g->ae_in=mymalloc(esize);
  26.         memset(g->ae_in,0,esize);
  27.         g->ae_out=mymalloc(esize);
  28.         memset(g->ae_out,0,esize);
  29.         g->ae_gen=mymalloc(esize);
  30.         memset(g->ae_gen,0,esize);
  31.         g->ae_kill=mymalloc(esize);
  32.         memset(g->ae_kill,0,esize);
  33.         p=g->end;
  34.         while(p){
  35.             memset(tmp,0,esize);
  36.             for(j=0;j<p->change_cnt;j++){
  37.                 i=p->change_list[j].v->index;
  38.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  39.                 if(i>=vcount) continue;
  40.                 bvunite(tmp,ae_kills[i],esize);
  41.             }
  42.             bvdiff(tmp,g->ae_gen,esize);
  43.             bvunite(g->ae_kill,tmp,esize);
  44.             i=p->expindex;
  45.             if(i>=0&&!BTST(g->ae_kill,i)) BSET(g->ae_gen,i);
  46.  
  47.             if(p==g->start) break;
  48.             p=p->prev;
  49.         }
  50.         if(g==fg){
  51.             memset(g->ae_in,0,esize);
  52.             memcpy(g->ae_out,g->ae_gen,esize);
  53.         }else{
  54.             memset(g->ae_out,UCHAR_MAX,esize);
  55.             bvdiff(g->ae_out,g->ae_kill,esize);
  56.         }
  57.         g=g->normalout;
  58.     }
  59.  
  60.     /*  ae_in und ae_out fuer jeden Block berechnen */
  61.     /*  out(b)=U-gen(B) vorinitialisiert und        */
  62.     /*  in(B0)=0, out(B0)=gen(B0)                   */
  63.     if(DEBUG&1024) {printf("pass:");pass=0;}
  64.     do{
  65.         if(DEBUG&1024) {printf(" %d",++pass);fflush(stdout);}
  66.         changed=0;
  67.         g=fg->normalout;    /*  in B0 aendert sich nichts   */
  68.         while(g){
  69.             struct flowlist *lp;
  70.             /*  in(B)=Schnitt out(P) mit P Vorgaenger von B */
  71.             lp=g->in;
  72.             i=0;    /*  Flag fuer ersten Vorgaenger */
  73.             while(lp){
  74.                 if(!lp->graph) ierror(0);
  75.                 if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  76.                     if(i){
  77.                         bvintersect(g->ae_in,lp->graph->ae_out,esize);
  78.                     }else{
  79.                         memcpy(g->ae_in,lp->graph->ae_out,esize);i=1;
  80.                     }
  81.                 }
  82.                 lp=lp->next;
  83.             }
  84.             /*  out(b)=gen(B) U (in(B)-kill(B)  */
  85.             memcpy(tmp,g->ae_in,esize);
  86.             bvdiff(tmp,g->ae_kill,esize);
  87.             bvunite(tmp,g->ae_gen,esize);
  88.             if(!bvcmp(tmp,g->ae_out,esize)){changed=1;memcpy(g->ae_out,tmp,esize);}
  89.             g=g->normalout;
  90.         }
  91.     }while(changed);
  92.     if(DEBUG&1024) printf("\n");
  93.     free(tmp);
  94. }
  95.  
  96.  
  97. int compare_objs(struct obj *o1,struct obj *o2,int t)
  98. /*  Vergleicht die beiden Objekte; liefert 0, wenn sie gleich sind, sonst   */
  99. /*  1 oder -1, um eine Ordnung darauf zu definieren                         */
  100. {
  101.     int i1,i2;
  102.     i1=o1->flags&~SCRATCH;i2=o2->flags&~SCRATCH;
  103.     if(i1<i2) return(-1);
  104.     if(i1>i2) return(1);
  105.     if(i1&KONST) return(compare_const(&o1->val,&o2->val,t));
  106.     if(i1&VAR){
  107.         i1=o1->v->index; i2=o2->v->index;
  108.         if(i1<i2) return(-1);
  109.         if(i1>i2) return(1);
  110.         i1=zl2l(o1->val.vlong); i2=zl2l(o2->val.vlong);
  111.         if(i1<i2) return(-1);
  112.         if(i1>i2) return(1);
  113.     }
  114.     return(0);
  115. }
  116.  
  117. int compare_exp(const void *a1,const void *a2)
  118. /*  Stub fuer compare_objs, damit als Vergleichsfunktion fuer qsort geht */
  119. {
  120.     struct IC *p1,*p2;int i1,i2;
  121.     p1=*((struct IC **)a1);p2=*((struct IC **)a2);
  122.     if(!p1||!p2) ierror(0);
  123.     i1=p1->code; i2=p2->code;
  124.     if(i1<i2) return(-1);
  125.     if(i1>i2) return(1);
  126.     i1=p1->typf; i2=p2->typf;
  127.     if(i1<i2) return(-1);
  128.     if(i1>i2) return(1);
  129.     i1=compare_objs(&p1->q1,&p2->q1,p1->typf);
  130.     if(i1) return(i1);
  131.     i1=compare_objs(&p1->q2,&p2->q2,p1->typf);
  132.     return(i1);
  133. }
  134. void print_ae(unsigned char *exp)
  135. {
  136.     int i;
  137.     if(!exp){ printf("available expressions not available\n"); return;}
  138.     for(i=0;i<ecount;i++)
  139.         if(BTST(exp,i))
  140.             {printf("%3d,%3d: ",elist[i]->expindex,i);pric2(stdout,elist[i]);}
  141. }
  142. void num_exp(void)
  143. /*  numeriert die Ausdruecke so, dass gleiche Ausdruecke die gleiche    */
  144. /*  nummer erhalten                                                     */
  145. {
  146.     struct IC *p;int c,i;
  147.     if(DEBUG&1024) printf("numerating expressions\n");
  148.     ecount=0;
  149.     if(DEBUG&1024){ printf("num_exp loop1\n");}
  150.     for(p=first_ic;p;p=p->next){
  151.         c=p->code;
  152.         if(p->z.flags&&p->q1.flags&&(c!=ASSIGN||(p->q1.flags&DREFOBJ))&&c!=MOVETOREG&&c!=MOVEFROMREG){
  153.             p->expindex=ecount++;
  154.             if(c==ADD||c==MULT||(c>=OR&&c<=AND)){
  155.                 if(p->q2.flags&&compare_objs(&p->q1,&p->q2,p->typf)<0&&(USEQ2ASZ||compare_objs(&p->q1,&p->z,p->typf))){
  156.                     struct obj o;
  157.                     o=p->q1;p->q1=p->q2;p->q2=o;
  158.                 }
  159.             }
  160.         }else p->expindex=-1;
  161.     }
  162.     elist=mymalloc(ecount*sizeof(struct IC *));
  163.     if(DEBUG&1024){ printf("num_exp loop2\n");}
  164.     for(p=first_ic;p;p=p->next){
  165.         if(p->expindex>=0){
  166.             elist[p->expindex]=p;
  167.         }
  168.     }
  169.     esize=(ecount+CHAR_BIT-1)/CHAR_BIT;
  170.     if(DEBUG&1024){ printf("%lu expressions, esize=%lu\nsorting expressions\n",(unsigned long)ecount,(unsigned long)esize);}
  171.     if(ecount>1) qsort(elist,ecount,sizeof(struct IC *),compare_exp);
  172.     if(DEBUG&1024){ printf("renumbering expressions\nnum_exp loop3\n");}
  173.     if(ecount>0){   /*  Aufpassen, da ecount unsigned!  */
  174.         for(c=0;c<ecount-1;c++){
  175.             if(!compare_exp(&elist[c],&elist[c+1]))
  176.                 elist[c+1]->expindex=elist[c]->expindex;
  177.         }
  178.     }
  179.     if(DEBUG&1024) printf("re-sorting expressions\n");
  180.     /*  wieder in die richtige Reihenfolge bringen  */
  181.     for(p=first_ic;p;p=p->next)
  182.         if(p->expindex>=0) elist[p->expindex]=p;
  183.     ae_globals=mymalloc(esize);
  184.     memset(ae_globals,0,esize);
  185.     ae_statics=mymalloc(esize);
  186.     memset(ae_statics,0,esize);
  187.     ae_address=mymalloc(esize);
  188.     memset(ae_address,0,esize);
  189.     ae_drefs=mymalloc(esize);
  190.     memset(ae_drefs,0,esize);
  191.     if(DEBUG&1024){ printf("num_exp loop4\n");}
  192.     ae_kills=mymalloc(vcount*sizeof(unsigned char *));
  193.     for(c=0;c<vcount;c++){
  194.         ae_kills[c]=mymalloc(esize);
  195.         memset(ae_kills[c],0,esize);
  196.     }
  197.     if(DEBUG&1024){ printf("num_exp loop5\n");}
  198.     for(c=0;c<ecount;c++){
  199.         struct Var *v;
  200. /*        if(c<ecount-1&&elist[c]==elist[c+1]) continue;*/  /*  gleiche ueberspringen   */
  201.         p=elist[c];
  202.         if(p->code==ADDRESS) continue;
  203.         if((p->q1.flags&(VAR|VARADR))==VAR){
  204.             v=p->q1.v;
  205.             i=v->index;
  206.             BSET(ae_kills[i],c);
  207.             if(p->q1.flags&DREFOBJ){ BSET(ae_kills[i+vcount-rcount],c);BSET(ae_drefs,c);}
  208.             if(v->nesting==0||v->storage_class==EXTERN) BSET(ae_globals,c);
  209.             if(v->storage_class==STATIC) BSET(ae_statics,c);
  210.             if(v->flags&USEDASADR) BSET(ae_address,c);
  211.         }
  212.         if((p->q2.flags&(VAR|VARADR))==VAR){
  213.             v=p->q2.v;
  214.             i=v->index;
  215.             BSET(ae_kills[i],c);
  216.             if(p->q2.flags&DREFOBJ){ BSET(ae_kills[i+vcount-rcount],c);BSET(ae_drefs,c);}
  217.             if(v->nesting==0||v->storage_class==EXTERN) BSET(ae_globals,c);
  218.             if(v->storage_class==STATIC) BSET(ae_statics,c);
  219.             if(v->flags&USEDASADR) BSET(ae_address,c);
  220.         }
  221.     }
  222. }
  223. void cse_replace(struct flowgraph *g,struct IC *p,struct IC *o,struct Var *v)
  224. /*  ersetzt die cse bei o zu p mit Variable v   */
  225. {
  226.     struct IC *n;
  227.     /*  Kopieranweisung erzeugen    */
  228.     if(DEBUG&1024) printf("cse_replace\n");
  229.     n=mymalloc(ICS);
  230.     n->line=o->line;
  231.     n->file=o->file;
  232.     n->code=ASSIGN;
  233.     n->typf=p->typf;
  234.     n->expindex=n->defindex=-1;
  235.     n->q1.flags=VAR;
  236.     n->q1.v=v;
  237.     n->q1.val.vlong=l2zl(0L);
  238.     n->q2.flags=0;
  239.     n->q2.val.vlong=szof(v->vtyp);
  240.     n->z=o->z;
  241.     /*  Die Kopieranweisung benutzt hoechstens, was die urspruengliche  */
  242.     /*  Operation benutzt hat+die Hulfsvariable und aendert nur, was    */
  243.     /*  die urspruengliche vorher geaendert hat.                        */
  244.     if(have_alias){
  245.         n->use_cnt=o->use_cnt+1;
  246.         n->use_list=mymalloc(n->use_cnt*VLS);
  247.         n->use_list[0].v=v;
  248.         n->use_list[0].flags=0;
  249.         memcpy(&n->use_list[1],o->use_list,o->use_cnt*VLS);
  250.         n->change_cnt=o->change_cnt;
  251.         n->change_list=o->change_list;
  252.     }
  253.     /*  evtl. FLussgraph korrigieren    */
  254.     if(g->end==o) g->end=n;
  255.     /*  einfuegen   */
  256.     insert_IC(o,n);
  257.     /*  Operation auf Hilfsvariable umlenken    */
  258.     o->z=n->q1;
  259.     /*  Operation aendert nun nur Hilfsvariable.   */
  260.     if(have_alias){
  261.         /*  Liste nicht freigeben, da sie umgebogen wird.   */
  262.         o->change_cnt=1;
  263.         o->change_list=mymalloc(VLS);
  264.         o->change_list[0].v=v;
  265.         o->change_list[0].flags=0;
  266.     }
  267. }
  268. void cse_search(struct flowgraph *g,struct IC *p,struct IC *o,struct Var *v,int global,unsigned char *bmk)
  269. /*  sucht die Quelle(n) fuer common subexpression und ersetzt sie   */
  270. /*  bmk ist Buffer, um zu merken, welche Bloecke schon besucht sind */
  271. {
  272.     struct flowlist *lp;
  273.     /*  Letzte Berechnung des Ausdrucks suchen, beginnend bei o */
  274.     /*  bei global kann o auch 0 sein!                          */
  275. /*    if(DEBUG&1024) printf("cse_search\n");*/
  276.     if(global){
  277.         if(BTST(bmk,g->index)) return;
  278.     }
  279.     while(o&&o->expindex!=p->expindex){
  280.         if(o==g->start) break;
  281.         o=o->prev;
  282.     }
  283.     if(!o&&!global) ierror(0);
  284.     if(o&&o->expindex==p->expindex){
  285.         if(!(o->z.flags&VAR)||o->z.v!=v)
  286.             cse_replace(g,p,o,v);
  287.         return;
  288.     }
  289.     if(!global) ierror(0);
  290.     /*  Block als besucht markieren, wenn er durchsucht wurde. Der  */
  291.     /*  erste Block bei globaler Suche muss beachtet werden und     */
  292.     /*  Endlosschleifen vermieden werden.                           */
  293.     if(o||!g->end) BSET(bmk,g->index);
  294.     lp=g->in;
  295.     while(lp){
  296.         if(!lp->graph) ierror(0);
  297.         if(lp->graph->branchout==g||!lp->graph->end||lp->graph->end->code!=BRA){
  298.             cse_search(lp->graph,p,lp->graph->end,v,global,bmk);
  299.         }
  300.         lp=lp->next;
  301.     }
  302. }
  303.  
  304. int cse(struct flowgraph *fg,int global)
  305. /*  common-subexpression-elimination; wenn global==0 werden nur einzelne    */
  306. /*  Bloecke betrachtet                                                      */
  307. {
  308.     struct flowgraph *g;struct IC *p,*o;int changed,i,j;
  309.     unsigned char *ae;struct Var *v;struct Typ *new;
  310.     if(DEBUG&1024) printf("common-subexpression-elimination\n");
  311.     changed=0;
  312.     ae=mymalloc(esize);
  313.     for(g=fg;g;g=g->normalout){
  314.         if(!global) memset(ae,0,esize); else memcpy(ae,g->ae_in,esize);
  315.         p=g->start;
  316.         while(p){
  317.             i=p->expindex;
  318.             if(i>=0){
  319.                 if(i>=ecount) ierror(0);
  320.                 if(BTST(ae,i)){
  321.                     if(DEBUG&1024){ printf("can eliminate common subexpression:\n");pric2(stdout,p);}
  322.                     /*  Hilfsvariable erzeugen  */
  323.                     new=mymalloc(TYPS);
  324.                     if(p->code==ADDRESS||p->code==ADDI2P||p->code==SUBIFP) new->flags=POINTER;
  325.                         else new->flags=p->typf;
  326.                     if(p->code==COMPARE||p->code==TEST) new->flags=0;
  327.                     if((new->flags&NQ)==POINTER){
  328.                         new->next=mymalloc(TYPS);
  329.                         new->next->flags=VOID;
  330.                         new->next->next=0;
  331.                     }else new->next=0;
  332.                     v=add_tmp_var(new);
  333.                     v->index=-1;
  334.                     /*  Operation durch assign Hilfsvariable ersetzen   */
  335.                     p->code=ASSIGN;
  336.                     p->typf=new->flags;
  337.                     p->q1.flags=VAR;
  338.                     p->q1.v=v;
  339.                     p->q1.val.vlong=l2zl(0L);
  340.                     p->q2.flags=0;
  341.                     p->q2.val.vlong=szof(new);
  342.                     if(global){
  343.                         unsigned char *bmk;size_t bsize;
  344.                         bsize=(basic_blocks+CHAR_BIT-1)/CHAR_BIT;
  345.                         bmk=mymalloc(bsize);
  346.                         memset(bmk,0,bsize);
  347.                         cse_search(g,p,0,v,global,bmk);
  348.                         free(bmk);
  349.                     }else cse_search(g,p,p->prev,v,global,0);
  350.                     changed=1;
  351.                     gchanged|=1;
  352.                 }else BSET(ae,i);
  353.             }
  354.             for(j=0;j<p->change_cnt;j++){
  355.                 i=p->change_list[j].v->index;
  356.                 if(p->change_list[j].flags&DREFOBJ) i+=vcount-rcount;
  357.                 if(i>=vcount) continue;
  358.                 bvdiff(ae,ae_kills[i],esize);
  359.             }
  360.  
  361.             if(p==g->end) break;
  362.             p=p->next;
  363.         }
  364.     }
  365.  
  366.     free(ae);
  367.     for(i=0;i<vcount;i++) free(ae_kills[i]);
  368.     free(ae_kills);
  369.     free(ae_globals);
  370.     free(ae_statics);
  371.     free(ae_address);
  372.     free(ae_drefs);
  373.     free(elist);
  374.  
  375.     return(changed);
  376. }
  377.